package com.fayou.algorithm.tree;

import sun.reflect.generics.tree.Tree;

public class Solution {
    public static void main(String[] args) {
        TreeNode treeNode = initTree();

        int i = maxDepth(treeNode);
        int i1 = minDepth(treeNode);

//        System.out.println("i：" +i+ ",i1:"+i1);


        preTraverseBTree(treeNode);
    }


    private static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        return 1 + Math.max(leftHeight, rightHeight);

    }


    private static int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null) {
            return minDepth(root.right) + 1;
        }
        if (root.right == null) {
            return minDepth(root.left) + 1;
        }

        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }


    private static void preTraverseBTree(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.val);
        preTraverseBTree(root.left);
        preTraverseBTree(root.right);
    }

    public static TreeNode initTree() {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
//        node3.left = node6;
//        node3.right = node7;
        node5.right = node8;
        node8.left = node9;
        return node1;
    }


    private static int maxDapth(TreeNode rootTree) {

        if (rootTree == null) {
            return 0;
        }
        return 1 + Math.max(maxDapth(rootTree.left), maxDapth(rootTree.right));
    }


    private static int minDapth(TreeNode rootTree){
        if (rootTree==null){
            return 0;
        }
        if (rootTree.left==null){
           return 1+ minDepth(rootTree.right);
        }

        if (rootTree.right==null){
            return  1+minDapth(rootTree.left);
        }

        return Math.min(minDepth(rootTree.left),minDepth(rootTree.right))+1;

    }

}
